package com.wc.alorithm_luogu.P1177;

import java.util.Scanner;

/**
 * @author congege
 * @create 2023:04:28 10:23
 * @describe https://www.luogu.com.cn/problem/P1177
 * 快速排序
 */
public class Main {
    public static void main(String[] args) {
        int[] array = new int[100001];
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        quickSort(array, 0, n - 1);
        StringBuilder ans = new StringBuilder();
        ans.append(array[0]);
        for (int i = 1; i < n; i++) {
            ans.append(" ");
            ans.append(array[i]);
        }
        System.out.println(ans);
    }

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int midIndex = left + (right - left) / 2;
//        int midIndex = left;
        int mid = array[midIndex];
        int i = left;
        int j = right;
        do {
            while (mid > array[i]) i++;
            while (mid < array[j]) j--;

            if (i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }
        } while (i <= j);

//        swap(array, midIndex, j);
        quickSort(array, left, j);
        quickSort(array, i, right);
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
